/*1 排序 2 查找 3 比较 ----RunTime: 380ms*/


#include <stdio.h>
#include <stdlib.h>

struct ListNode{
    int val;
    struct ListNode *next;
};

typedef struct ListNode Node, *PNode;

void print(struct ListNode* p)
{
	struct ListNode* q;
	for(q = p; q != NULL; q = q->next)
		printf("[%d]", q->val);
	printf("\n");
}

int isEmpty(PNode head) 
{ 
	if(head->next == NULL) 
	{ 
		return 1; 
	} 
	else 
	{ 
		return 0; 
	}
}

PNode reverseLinkList(PNode head) 
{ 
	if(isEmpty(head)) 
	{ 
		return head; 
	} 
	PNode rHead = (PNode)malloc(sizeof(Node)); 
	rHead->next = NULL; 
	PNode tmp = head->next, tmpNext; 
	while(tmp != NULL) 
	{ 
		if(tmp->next != NULL) 
		{ 
			tmpNext = tmp->next; 
		} 
		else 
		{ 
			tmpNext = NULL; 
		} 
		tmp->next = rHead->next; 
		rHead->next = tmp; 
		tmp = tmpNext; 
	} 
	return rHead; 
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    PNode link1 = reverseLinkList(l1);
	PNode link2 = reverseLinkList(l2);
	
	struct ListNode *result = (PNode)malloc(sizeof(Node)); 
	result->next = NULL; 
	PNode p = result;

	PNode p1 = link1->next, p2 = link2->next;
	int carry = 0, addResult;
	PNode tmp;
	printf("p1%p p2%p\n", p1, p2);
	while(p1!= NULL && p2 != NULL) {
		addResult = carry + p1->val + p2->val;
		if(addResult / 10) {
			carry = 1;
			addResult = addResult % 10;
		}
		else {
			carry = 0;
		}
		tmp = (PNode)malloc(sizeof(Node));
		tmp->next = NULL;
		tmp->val = addResult;
		p->next = tmp;
		p = p->next;
		p1 = p1->next;
		p2 = p2->next;
		printf("p%d %p %p\n", p->val, p, p->next);
	}
	printf("ret%d %p %p\n", result->val, result, result->next);

	while(p1 != NULL) {
		addResult = carry + p1->val;
		if(addResult / 10) {
			carry = 1;
			addResult = addResult % 10;
		}
		else {
			carry = 0;
		}
		tmp = (PNode)malloc(sizeof(Node));
		tmp->next = NULL;
		tmp->val = addResult;
		p->next = tmp;
		p = p->next;
		p1 = p1->next;
	}
	while(p2 != NULL) {
		addResult = carry + p2->val;
		if(addResult / 10) {
			carry = 1;
			addResult = addResult % 10;
		}
		else {
			carry = 0;
		}
		tmp = (PNode)malloc(sizeof(Node));
		tmp->next = NULL;
		tmp->val = addResult;
		p->next = tmp;
		p = p->next;
		p2 = p2->next;
	}

	return result;
}

int main(void)
{
	struct ListNode* plista, *plistb, *tmp;
	
	plista = (struct ListNode *)malloc(sizeof(struct ListNode));
	plistb = (struct ListNode *)malloc(sizeof(struct ListNode));
	
	plista->val = 2;
	plista->next = NULL;
	plistb->val = 5;
	plistb->next = NULL;
	
	tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	tmp->next = plista->next;
	tmp->val = 4;
	plista->next = tmp;
	tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	tmp->next = plistb->next;
	tmp->val = 6;
	plistb->next = tmp;
	
	tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	tmp->next = plista->next;
	tmp->val = 3;
	plista->next = tmp;
	tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	tmp->next = plistb->next;
	tmp->val = 4;
	plistb->next = tmp;
	
	print(addTwoNumbers(plista, plistb));
	return 0;
}